1458A - Row GCD - CodeForces Solution

#include <bits/stdc++.h>
// #include <x86intrin.h>
// #include <sys/resource.h>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
using namespace std;
// using namespace __gnu_pbds;

// Pragmas
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2")

#define v vector
// Aliases
using ll = long long;
using ull = unsigned long long;
using ld = long double;
// template<typename T>
// using oset =  tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

// Constants
constexpr ll INF = 4e18;
constexpr ld EPS = 1e-9;
constexpr ll MOD = 1e9 + 7;
constexpr ll mod_cf = 998244353;

// Macros
#define F first
#define S second
#define all(x) begin(x), end(x)
#define allr(x) rbegin(x), rend(x)
#define int long long
#define pb push_back
#define py cout << "YES\n";
#define pm cout << "-1\n";
#define pn cout << "NO\n";
// #define readv(x, n) vi x(n); forn(i,0,n) scanf("%d", &x[i])
#define fl(i, n) for (int i = 0; i < n; i++)

int find_exp(int x, int y, int mod)
{
    if (y == 0)
        return 1;
    if (y == 1)
        return x % mod;
    int temp = find_exp(x, y / 2, mod) % mod;
    if (y % 2 == 0)
        return (temp * temp % mod) % mod;
    else
        return ((x % mod) * (temp * temp % mod) % mod) % mod;
}

int inverse(int x, int mod)
{
    return find_exp(x, mod - 2, mod);
}

int gp_sum(int base, int power)
{
    int x = (find_exp(base, power + 1, MOD) - 1 + MOD) % MOD;
    int y = inverse(base - 1, MOD);
    return (x * y) % MOD;
}

vector<int> fact(2000001, 1);

void sieveOfEratosthenes(int N, int s[])
{
    // Create a boolean array "prime[0..n]" and
    // initialize all entries in it as false.
    vector<bool> prime(N + 1, false);

    // Initializing smallest factor equal to 2
    // for all the even numbers
    for (int i = 2; i <= N; i += 2)
        s[i] = 2;

    // For odd numbers less than equal to n
    for (int i = 3; i <= N; i += 2)
    {
        if (prime[i] == false)
        {
            // s(i) for a prime is the number itself
            s[i] = i;

            // For all multiples of current prime number
            for (int j = i; j * i <= N; j += 2)
            {
                if (prime[i * j] == false)
                {
                    prime[i * j] = true;

                    // i is the smallest prime factor for
                    // number "i*j".
                    s[i * j] = i;
                }
            }
        }
    }
}

// Function to generate prime factors and its power
vector<pair<int, int>> generatePrimeFactors(int N)
{
    // s[i] is going to store smallest prime factor
    // of i.
    int s[N + 1];

    // Filling values in s[] using sieve
    sieveOfEratosthenes(N, s);
    vector<pair<int, int>> vec;
    int curr = s[N]; // Current prime factor of N
    int cnt = 1;     // Power of current prime factor

    // Printing prime factors and their powers
    while (N > 1)
    {
        N /= s[N];

        // N is now N/s[N]. If new N als has smallest
        // prime factor as curr, increment power
        if (curr == s[N])
        {
            cnt++;
            continue;
        }

        vec.emplace_back(curr, cnt);

        // Update current prime factor as s[N] and
        // initializing count as 1.
        curr = s[N];
        cnt = 1;
    }
    return vec;
}

void solve()
{
    int n, m; cin >> n >> m;
    vector<int> a(n), b(m);
    fl(i, n) cin >> a[i];
    fl(i, m) cin >> b[i];
    sort(all(a));
    int g = 0;
    for(int i = 1; i<n; i++){
        g = __gcd(g, a[i] - a[i-1]);
    }
    for(int i = 0; i<m; i++){
        cout << __gcd(g, a[0] + b[i]) << " ";
    }
}

int32_t main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    for (int i = 1; i <= 2000000; i++)
        fact[i] = (fact[i - 1] * i) % MOD;
    // cin >> t;
    while (t--)
    {
        solve();
    }
}